package main.leetcode.primary.from201to300;

public class ex215 {
    public static void main(String[] args) {
        for (int i = 0; i < 10; ++i) {
            System.out.println(
                    new ex215().findKthLargest(new int[] {3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));
        }
    }

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        int tar = nums.length - k;
        while (true) {
            int index = partition(nums, left, right);
            if (index == tar) {
                return nums[index];
            } else if (index < tar) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
    }

    private int partition(int[] nums, int l, int r) {
        int index = l + (int) (Math.random() * (r - l + 1));
        swap(nums, l, index);
        int pivot = nums[l];
        int i = l + 1, j = r;
        while (true) {
            while (i < r && nums[i] < pivot) {
                ++i;
            }
            while (l < j && nums[j] > pivot) {
                --j;
            }
            if (i >= j) {
                break;
            }
            swap(nums, i++, j--);
        }
        swap(nums, l, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
